package com.cat.graphTheory;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-100-liked
 * @create 2025/9/24 20:27
 * @since JDK17
 */

public class Solution33 {
    static Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        int x = nums[random.nextInt(0, nums.length)];
        int[] big = Arrays.stream(nums).filter(num -> num > x).toArray();
        int[] small = Arrays.stream(nums).filter(num -> num < x).toArray();
        int[] equal = Arrays.stream(nums).filter(num -> num == x).toArray();
        if (big.length <= k) {
            return findKthLargest(big, k);
        }
        if (k > big.length + equal.length) {
            return findKthLargest(small, k - big.length - equal.length);
        }
        return x;
    }
}
